<Day9- 排序&搜尋sort>

排序演算法
從慢到快

1. 冒泡排序：basic 中的basic
   • 修改- 內迴圈扣掉外迴圈重複的部分
2. 選擇排序：原址比較排序 找到最小的放到第一 then 找第二小的
3. 插入排序：每排一格陣列 以此方式建構最後的排序陣列
4. 合併排序：分治演算法 利用recursion
   • 將原始陣列切分成較小的陣列 直到每個小陣列只有一個位置 接著將小陣列合併成較大的陣列直到最後一個排序完畢的陣列
5. 快速排序 複雜度O(nlogn) 但效能高於其他相同複雜度的
   • 使用分治的方法 將原始陣列分為較小的陣列

搜尋演算法
之前BinarySearchTree的search , LinkedList 的indexOf都是

1. 循序搜尋=線性搜尋：將每一個資料結構中的元素和目標做比較 最低效的方法
2. 二分搜尋：要求被搜尋的資料結構已排序了
   • 找中間值,如果是就是了, 太高 找右邊重來; 太低 找左邊重來

//排序&搜尋

function ArrayList(){
  let array = []

  this.insert = function(item){
    array.push(item)
  }
  this.toString = () => array.join()

  //會用到的函數
  const swap = function(index1, index2){
    let aux = array[index1]
    array[index1] = array[index2]
    array[index2] = aux
  }
  //合併的遞迴
  const mergeSortRec = function(array){
    let length = array.length
    if(length == 1){
      return array
    }
    let mid = Math.floor(length/2), left = array.slice(0,mid), right = array.slice(mid, length)

    return merge(mergeSortRec(left),mergeSortRec(right))
  }
  const merge = function(left , right){
    let result = [], il = 0, ir = 0
    while(il <left.length && ir< right.length){
      if(left[il] < right[ir]){
        result.push(left[il++])
      }else{
        result.push(right[ir++])
      }
    }
    while(il < left.length){
      result.push(left[il++])
    }
    while(ir < right.length){
      result.push(right[ir++])
    }
    return result
  }
  //快速的迴圈
  const quick = function(array, left, right){
    let index

    if(array.lenth > 1){

      index = partition(array, left, right)

      if (left < index - 1){
        quick (array, left, index-1 )
      }
      if (index < right){
        quick(array, index, right)
      }
    }
  }
  const partition = function(array, left, right){
    let pivot = array[Math.floor((right+left)/2)], i = left, j = right

    while (i <= j){
      while(array[i]< pivot){i++}
      while(array[i]>pivot){j--}
      if( i <= j){
        swapQuickStort(array, i ,j )
        i++
        j--
      }
    }
    return i
  }
  const swapQuickStort = function(array, index1, index2){
    let aux = array[index1]
    array[index1] = array[index2]
    array[index2] = aux
  }
  

  //排序
  //1.冒泡排序
  this.bubbleSort = function(){
    let length = array.length
    for (var i = 0; i < length; i++) {
      for (var j = 0; j < length-1; j++) {
        if(array[j] > array[j+1]){
          swap(j, j+1)
        }
      }
    }
  }//O(n^2)
  this.bubbleSortAdv = function(){
    let length = array.length
    for (var i = 0; i < length; i++) {
      for (var j = 0; j < length-1-i; j++) {
        if(array[j] > array[j+1]){
          swap(j, j+1)
        }
      }
    }
  }//O(n^2)

  //2.選擇排序
  this.selectionSort = function(){
    let length = array.length, indexMin
    for (var i = 0; i < length; i++) {
      index = i
      for (var j = i; j < length; j++) {
        if(array[indexMin] > array[j]){
          indexMin = j
        }
      }
      if(i !== indexMin){
        swap(i, indexMin)
      }
    }
  }//O(n^2)

  //3.插入排序
  this.insertionSort() = function(){
    let length = array.length,j, temp
    for (var i =1; i<length ; i++){
      j = i
      temp = array[i]
      while(j>0 && array[j-1]> temp){
        array[j] = array[j-1]
        j--
      }
      array[j] = temp
    }
  }
  
  //4.合併排序
  this.mergeSort = function(){
    array = mergeSortRec(array)
  }//O(nlogn)

  //5.快速排序
  this.quickSort = function(){
    quick(array, 0, array.length -1 )
  }//O(nlogn)



  //搜尋
  //1.循序搜尋
  this.sequentialSearch = function(item){
    for (var i = 0; i < array.length; i++) {
      if( item === array[i]){
        return i
      }
    }
    return -1
  }
  //2.二分搜尋
  this.binarySearch = function(item){
    this.quickSort()

    let low = 0 , high = array.length - 1 , mid , element

    while (low <= high){
      mid = Math.floor((low+hight)/2)
      element = array[mid]
      if(element < item){
        low = mid + 1
      }else if(element > item){
        high = mid -1
      }else {
        return mid
      }
    }
    return -1
  }
}

//測試
function createNonSortedArray(size){
  let array = new ArrayList()
  for ( let i = size; i >0 ; i--){
    array.insert(i)
  }
  return array
}

var array = createNonSortedArray(5)
console.log(array.toString())
array.bubbleSort()
console.log(array.toString())
array.selectionSort()
console.log(array.toString())
array.mergeSort()
console.log(array.toString())
array.quickSoty()
console.log(array.toString())